package code101_200.code1_10;

import com.sun.source.tree.Tree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class _104maxDepthOfTree {

    /**
     * 初始考虑，层次遍历即可。思考了一下，层次遍历只能找到最深的节点编号，很难判断深度。如果需要的话则要重新遍历。比较耗时
     * 重新考虑：使用深搜，是个动态规划问题，每次判断子树和目前树的最大值。
     * 重新考虑：深搜过程中需要额外的数组空间保存每列的高度，不然会丢失信息。而层次遍历自带层数，可直接使用
     *
     * 层序遍历：
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 20.51%     * 的用户
     * 内存消耗：     * 38.5 MB     * , 在所有 Java 提交中击败了     * 40.37%     * 的用户
     * @param root
     * @return
     */
    public int maxDepthOfBFS(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        TreeNode node;
        if(root==null)return 0;
        int maxDepth = 0;
        int size = 0;
        deque.add(root);
        while (deque.size()!=0){
            size = deque.size();
            maxDepth++;
            for (int i = 0; i < size; i++) {
                node = deque.poll();
                if(node.left!=null) deque.add(node.left);
                if(node.right!=null) deque.add(node.right);
            }
        }
        return maxDepth;
    }

    /**
     * 可以使用树本身结果val存储树目前的深度值
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 20.51%     * 的用户
     * 内存消耗：     * 38.2 MB     * , 在所有 Java 提交中击败了     * 70.81%     * 的用户
     * 注：时间效率上还是上不去，看来得更换方案
     * @param root
     * @return
     */
    public int maxDepthOfDFS(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = new TreeNode();
        int max = 1;
        if(root==null) return 0;
        root.val = 1;
        stack.add(root);
        while (stack.size()!=0){
            node = stack.pop();
            max = node.val>max?node.val:max;
            if(node.left!=null){
                node.left.val = max+1;
                stack.add(node.left);
            }
            if(node.right!=null){
                node.right.val = max+1;
                stack.add(node.right);
            }
        }
        return max;
    }
}
